/**
 * 46. 全排列
 * https://leetcode-cn.com/problems/permutations/
 */
const { displayNestedArray } = require('../../libs/public');

/**
 * @param {number[]} nums
 * @param {number} begin
 * @return {number[][]}
 */
function subPermute(nums, begin) {
  const { length } = nums;
  const num = nums[begin];
  if (begin === length - 1) return [[num]];
  const lists = subPermute(nums, begin + 1);
  return lists.reduce((total, list) => {
    const count = list.length;
    for (let i = 0; i <= count; i += 1) {
      const newList = Array.from(list);
      newList.splice(i, 0, num);
      total.push(newList);
    }
    return total;
  }, []);
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function permute(nums) {
  return subPermute(nums, 0);
}

console.log(displayNestedArray(permute([1, 2, 3])));
console.log(displayNestedArray(permute([0, 1])));
console.log(displayNestedArray(permute([1])));
console.log(displayNestedArray(permute([1, 2, 3, 4])));
